package cn.edu.xjtu.work.lengthOfLongestSubstring;

/**
 * 3. 无重复字符的最长子串
 * 
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 */

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class Solution {
  public static void main(String[] args) {
    // String s = "abcabcbb";
    // String s = "pwwkew";
    // String s = " ";
    String s = "dvdf";
    System.out.println(lengthOfLongestSubstring1(s));
  }

  /**
   * 第一种解法,滑动窗口
   * 
   * 使用队列模拟窗口,每次从中取出一个元素,并向字符串右侧扫描,如果队列中无该元素则加入,如果有则停止扫描,直到扫描完全部元素
   * 
   * @param s 输入字符串
   * @return 字串的最大长度
   */
  public static int lengthOfLongestSubstring(String s) {
    int maxLength = 0;
    Queue<Character> queue = new LinkedList<Character>();
    queue.offer('1');// 占位

    for (int i = 0; i < s.length(); i++) {
      queue.poll();
      int right = i + queue.size();// 表示接下来应该扫描哪一个元素
      if (right <= s.length() - 1)
        while (!queue.contains(s.charAt(right))) {
          queue.offer(s.charAt(right));// 当队列中不包含该元素时入队
          right += right < s.length() - 1 ? 1 : 0;// 右指针加一
        }
      maxLength = Math.max(maxLength, queue.size());
    }

    return maxLength;
  }

  /**
   * 第二种解法,使用哈希表来存储数据
   * 
   * 通过遍历字符串判断是否在表中是否已经有该字符,如果没有,将其加入,如果有,则将该字符及其之前的所有字符全部取出
   * 
   * 问题:在查找到一个重复元素去掉前面所有字符需要遍历一遍哈希表,时间复杂度太高,提交时超过时间限制
   * 
   * @param s 输入字符串
   * @return 字串的最大长度
   */
  public static int lengthOfLongestSubstring1(String s) {
    int maxLength = 0;
    Map<Character, Integer> map = new HashMap<>();
    int i = 0;
    int lastEdit = 0;// 上次重复字符出现的位置
    while (true) {
      if (i == s.length())
        break;
      char c = s.charAt(i);
      if (map.containsKey(c)) {
        maxLength = Math.max(maxLength, map.size());
        int index = map.remove(c);
        lastEdit = index;
        Collection<Integer> values = map.values();
        for (int j = lastEdit; j < index; j++) {
          values.remove(j);
        }
      }
      map.put(c, i);
      i++;
    }
    maxLength = Math.max(maxLength, map.size());
    return maxLength;
  }

  /**
   * 题解答案,滑动窗口
   * 
   * 类似于第一种解法
   * 
   * @param s
   * @return
   */
  public static int lengthOfLongestSubstringAnswer(String s) {
    // 哈希集合，记录每个字符是否出现过
    Set<Character> occ = new HashSet<Character>();
    int n = s.length();
    // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
    int rk = -1, ans = 0;
    for (int i = 0; i < n; ++i) {
      if (i != 0) {
        // 左指针向右移动一格，移除一个字符
        occ.remove(s.charAt(i - 1));
      }
      while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
        // 不断地移动右指针
        occ.add(s.charAt(rk + 1));
        ++rk;
      }
      // 第 i 到 rk 个字符是一个极长的无重复字符子串
      ans = Math.max(ans, rk - i + 1);
    }
    return ans;
  }

}
